package 二叉树;

public class LC_654z最大二叉树 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public TreeNode constructMaximumBinaryTree(int[] nums){
        return constructMaximumBinaryTree1(nums,0,nums.length);
    }
    public TreeNode constructMaximumBinaryTree1(int[] nums,int leftindex,int rightindex) {
        if(rightindex-leftindex<1) return null;
        if(rightindex-leftindex==1)
            return new TreeNode(nums[leftindex]);
        int index=leftindex;
        int maxValue=nums[index];
        //中
        for(int i=leftindex+1;i<rightindex;i++){
            if(maxValue<nums[i]){
                maxValue=nums[i];
                index=i;
            }
        }
        TreeNode node=new TreeNode(maxValue);
        //左
        node.left=constructMaximumBinaryTree1(nums,leftindex,index);
        //右
        node.right=constructMaximumBinaryTree1(nums,index+1,rightindex);
        return node;
    }
}
